//
// Created by Administrator on 2021/5/18.
//
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int countTriplets(vector<int> &arr) {
        // 找到两部分相等，等效于找到一个子序列，异或和为0
        int n = (int) arr.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int temp = arr[i];
            for (int j = i + 1; j < n; ++j) {
                temp ^= arr[j];
                if (temp == 0 and j - i >= 1) {
                    ans += (j - i); // 贡献为长度-1
                }
            }
        }
        return ans;
    }
};

class Solution2 { //优秀题解
public:
    int countTriplets(vector<int> &arr) {
        for (int i = 1; i < arr.size(); ++i) {
            arr[i] ^= arr[i - 1];
        }
        int ans = 0;
        unordered_map<int, vector<int>> record;
        record[0].push_back(-1);
        for (int i = 0; i < arr.size(); ++i) {
            if (record.find(arr[i]) != record.end()) {
                for (const int index:record[arr[i]]) {
                    ans += i - index - 1;
                }
            }
            record[arr[i]].push_back(i);
        }
        return ans;

    }
};


int main() {
    vector<int> v1{2, 3, 1, 6, 7};
    vector<int> v2{1, 1, 1, 1, 1};
    vector<int> v3{2, 3};
    vector<int> v4{1, 3, 5, 7, 9};
    vector<int> v5{7, 11, 12, 9, 5, 2, 7, 17, 22};
    Solution sol;
    cout << sol.countTriplets(v1) << endl;
    cout << sol.countTriplets(v2) << endl;
    cout << sol.countTriplets(v3) << endl;
    cout << sol.countTriplets(v4) << endl;
    cout << sol.countTriplets(v5) << endl;
    return 0;
}